/**
 * 归并排序（自底向上）
 */
public class MergeBUSort extends MergeSort {
    private Comparable[] aux;

    @Override
    void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];

        // 进行 lgN次两两归并
        for (int sz = 1; sz < N; sz = sz + sz) { // sz子数组大小
            for (int lo = 0; lo < N - sz; lo += sz + sz) { // lo：子数组索引
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz -1, N - 1));
            }
        }
    }

    public static void main(String[] args) {
        TemplateSort templateSort = new MergeSort();

        Comparable[] data = templateSort.createInt(0, 1000, 300);

        templateSort.run(data);
    }
}
